Some computer software is operated by the use of commands. Each command contains one or more tokens. A token is a part of a command that may be made up of one or more characters, including spaces.
For example, the commands "Go to the store" and "Go to the park" are two commands that could be interpreted by an individual. The first token "Go" can be followed by the second token "to the store" to indicate an acceptable command. "Sit down" is yet another acceptable command with tokens "sit" and "down". However, "Sit to the store" is not an acceptable command.
When a command is received by computer software, the computer software attempts to determine what action is indicated by the command. One way of performing this function is to compare the command submitted with a list of acceptable commands. Each acceptable command in the list may also contain an action that is to be performed to carry out the command. If the submitted command matches an acceptable command, the corresponding action of the acceptable command is performed to execute the submitted command.
While such a system can assist the computer software in carrying out the submitted commands, it can have several drawbacks. First, the more acceptable commands there are, the longer it can take to search all of them in order to match the submitted command. Second, if the number of acceptable commands is large, it can require a great deal of storage space to store all acceptable commands.
The list of acceptable commands can be stored in a tree structure to reduce the space required to store all of the acceptable commands. The root nodes of the tree can contain acceptable first tokens in a command. In the example, above, "Go" and "Sit" are acceptable first tokens. The tree can store one of these tokens in each of the two root nodes. The tokens, "to the store" and "to the park" are acceptable second tokens, but only for those commands following the token "Go". To indicate this relationship, nodes containing "to the store" and "to the park" may be stored as descendant nodes of the node containing the token "Go". This structure can reduce the overall storage space required to store acceptable commands, because "Go" is only stored once, even though it can be used in two acceptable commands. The other root node containing the token "Sit" has only one descendant node containing the token "down" to indicate "Sit down" is an acceptable command. The tree can be searched to match the submitted command, token by token. The process can stop after the first match is found, or if multiple matches are possible, after the tree has been fully searched for all matching acceptable commands for the submitted command.
The tree structure can be used to simplify the search for acceptable commands. If a submitted command is "Sit down", comparing the first token "Sit" in the submitted command, with the first root node "Go" will result in no match. It is not necessary to attempt to match the second token in the submitted command with the tokens of the descendant nodes of the node containing the token "Go" because an acceptable command will not result due to the lack of a match with the tokens in the root node. Thus, searching time for a matching acceptable command can be less than attempting to match all acceptable commands.
The tree structure can even assist in matching the tokens. Each node can contain a function that determines whether the token in the submitted command matches the acceptable tokens for the node. The node can approve even partial matches between the submitted token and the acceptable token, allowing "store" to match "to the store". This allows commands to be shortened by frequent users of the computer program who know how to provide terse commands. Thus the submitted command "Go store" will cause the computer program to perform the same action as the submitted command "Go to the store".
Although the method described above can work better than searching all of the acceptable commands, it may still have problems associated with it. Some computer programs can have hundreds of acceptable commands, so even using the structure and method described above can take an unacceptably long amount of time.
Often, commands will be received in groups, with each command in the group differing only slightly from other commands in the group. For example, assume a tree of acceptable commands with the root nodes having one of the tokens "A" through "Z", descendant nodes of node Z are nodes having one of the tokens "A1" through "Z1", descendant nodes of the node with the token "Z1" include nodes containing one of the tokens "a" through "z" and descendant nodes of the node containing the token "z" contain one of the tokens "a2" through "z2". Assume for example a first submitted command received is "Z Z1 z y2". There may be a high probability that the second submitted command will begin with the same tokens, such as the submitted command "Z Z1z z2". After receiving and matching the first command with an acceptable command, matching the second submitted command with an acceptable command requires searching the tree again starting at the first root node, for example, at the node having a matching token A. Comparing the first token in the submitted command "Z" with the token "A" stored in the first root node will fail, as will the other comparisons "B" through "Y".
What is needed is a method and apparatus that can efficiently attempt to match to an acceptable command a submitted command that follows a similar submitted command.